"""
TimSort是一种稳定的、自适应的、迭代的归并排序，在部分排序数组上运行时需要的比较远远少于nlg (n)次，
而在随机数组上运行时提供与传统归并排序相当的性能。
像所有合适的归并排序一样，这种排序是稳定的，运行时间为O(n log n)(最坏情况)。
在最坏的情况下，这种排序需要n/2个对象引用的临时存储空间;在最好的情况下，它只需要少量的常量空间。

详情见: http://svn.python.org/projects/python/trunk/Objects/listsort.txt
"""


def insertion_sort(arr, left=0, right=None):
    if right is None:
        right = len(arr) - 1

    for i in range(left + 1, right + 1):
        key_item = arr[i]
        j = i - 1
        while j >= left and arr[j] > key_item:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key_item

    return arr


def merge(left, right):
    if not left:
        return right

    if not right:
        return left

    if left[0] < right[0]:
        return [left[0]] + merge(left[1:], right)

    return [right[0]] + merge(left, right[1:])


def timsort(arr: list):
    min_run = 32
    n = len(arr)

    for i in range(0, n, min_run):
        insertion_sort(arr, i, min((i + min_run - 1), n - 1))

    size = min_run
    while size < n:
        for start in range(0, n, size * 2):
            mid = start + size - 1
            end = min((start + size * 2 - 1), (n - 1))
            merged_array = merge(
                left=arr[start: mid + 1], right=arr[mid + 1: end + 1]
            )
            arr[start: start + len(merged_array)] = merged_array

        size *= 2

    return arr


print(timsort([3, 5, 2, 6, -12, 91, 36, 123, 687, 0, -31, -81]))

import numpy as np

rng = np.random.default_rng(0)
a = rng.integers(-100, 100, size=100).tolist()
print(a)
timsort(a)
print(a)
